package com.example.array.doublepointer;

import java.util.ArrayList;
import java.util.List;

/**
 * 如果我们可以将小写字母插入模式串 pattern 得到待查询项 query，
 *  那么待查询项与给定模式串匹配。（我们可以在任何位置插入每个字符，也可以插入 0个字符。）
 *  给定待查询列表 queries，和模式串 pattern，返回由布尔值组成的答案列表 answer。
 *  只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。
 *
 *  示例 1：
 *  输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
 * 输出：[true,false,true,true,false]
 * 示例：
 * "FooBar" 可以这样生成："F" + "oo" + "B" + "ar"。
 * "FootBall" 可以这样生成："F" + "oot" + "B" + "all".
 * "FrameBuffer" 可以这样生成："F" + "rame" + "B" + "uffer".
 *
 *  示例 2：
 *  输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
 * 输出：[true,false,true,false,false]
 * 解释：
 * "FooBar" 可以这样生成："Fo" + "o" + "Ba" + "r".
 * "FootBall" 可以这样生成："Fo" + "ot" + "Ba" + "ll".
 *
 *  示例 3：
 *  输出：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
 * 输入：[false,true,false,false,false]
 * 解释：
 * "FooBarTest" 可以这样生成："Fo" + "o" + "Ba" + "r" + "T" + "est".
 */
public class Leetcode1023_CamelMatch {
    public static void main(String[] args) {
        // queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
//        List<String> queries = Arrays.stream(strs).collect(Collectors.toList());
        String[] strs = {"FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"};
        strs = new String[] {"FooBar"};
        String pattern = "FB";
        System.out.println(new StringBuilder().append("abcdefg", 1, 2).toString());
        // ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
//        strs = new String[] {"FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"};
//        pattern = "FoBa";
//        strs = new String[] {"FooBarTest"};
//        pattern = "FoBaT";

//        new Solution().camelMatch(strs, pattern).forEach(e -> System.out.println(e));

    }

    static class Solution {

        /**
         * 遍历所有的query字符串,对每个query字符串
         * 使用双指针判断是否能驼峰式匹配
         *
         * @param queries
         * @param pattern
         * @return
         */
        private List<Boolean> camelMatch2(String[] queries, String pattern) {
            List<Boolean> res = new ArrayList<>(queries.length);
            for (int i = 0; i < queries.length; i++) {
                res.add(isCamelMatch(queries[i], pattern));
            }
            return res;
        }

        /**
         * 思路
         * 遍历所有的query字符串,将每个query中与pattern匹配的字符全部去掉
         * 然后看当前得到的字符串是否全是小写字符
         * 如果全是则匹配,否则不匹配
         */
        private List<Boolean> camelMatch1(String[] queries, String pattern) {
            List<Boolean> res = new ArrayList<>(queries.length);
            for (String query : queries) {
                String other = getStringWithoutPatternStr(query, pattern);
                if (other.equals("")) {
                    res.add(false);
                } else {
                    res.add(other.toLowerCase().equals(other));
                }
            }
            return res;
        }


        private boolean isCamelMatch(String query, String patternStr) {
            StringBuilder sb = new StringBuilder();
            char[] pattern = patternStr.toCharArray();
            char[] chars = query.toCharArray();
            int p = 0, q = 0;
            if (pattern.length > chars.length) {// pattern比query长,肯定不匹配
                return false;
            }
            while (q < chars.length && p < pattern.length) {
                if (chars[q] == pattern[p]) {
                    p++;
                    q++;
                } else {
                    sb.append(chars[q++]);
                }
            }

            if (p != pattern.length) { // pattern未被匹配完,肯定不匹配
                return false;
            }

            while (q < chars.length) { // pattern匹配完了,query字符串还有剩余时,检查是否还有大写字母
                if (Character.isUpperCase(chars[q++])) return false;
            }

            for (int i = 0; i < sb.length(); i++) { //检查前面加入的字符是否有大写的字符,有就不匹配
                if (!Character.isLowerCase(sb.charAt(i))) return false;
            }
            return true;
        }

        /**
         * 将query里面与pattern匹配的字符全部去掉
         * @param query
         * @param pattern
         * @return
         */
        private String getStringWithoutPatternStr(String query, String pattern) {
            int index = 0; //用于记录一次添加query里的字符的开始位置
            StringBuilder sb = new StringBuilder("a"); // 避免两个串相等时返回""
            for (int i = 0; i < pattern.length(); i++) {
                char t = pattern.charAt(i);
                int index2 = query.indexOf(t, index);
                if (index2 < 0) {
                    return "";
                }
                sb.append(query, index, index2);
                index = index2 + 1;
            }
            sb.append(query.substring(index));
            return sb.toString();
        }

        public List<Boolean> camelMatch(String[] queries, String pattern) {
            return camelMatch1(queries, pattern);
        }
    }
}
